package com.fanshuai.algorithms.dynamic;

import com.fanshuai.algorithms.datastructure.tree.binarytree.IntListValue;

import java.util.ArrayList;
import java.util.List;

public class Bag {
    /**
     * 01背包问题（01 knapsack problem）：一共有N件物品，第i件物品的重量为w[i]，价值为v[i]。
     * 在总重量不超过背包承载上限W的情况下，能够装入背包的最大价值是多少？
     *
     * @param weight 物品重量
     * @param v  物品价值
     * @param W  背包重量
     * @return
     */
    public static int knapsack(int[] weight, int[] v, int W) {
        return knapsack0(weight, v, 0, W);
    }

    /**
     * 0-1背包问题， 递归解决
     * 背包问题为组合问题，递归层数为0-len, 分0和1两个分支。通过背包重量W剪枝
     * @param weight
     * @param v
     * @param n
     * @param W
     * @return
     */
    private static int knapsack0(int[] weight, int[] v, int n, int W) {
        if (n == weight.length) {
            return 0;
        }
        if (W < weight[n]) {
            return 0;
        }

        int v0 = knapsack0(weight, v, n + 1, W);  //0分支
        int v1 = v[n] + knapsack0(weight, v, n + 1, W - weight[n]);  //1分支

        return Math.max(v0, v1);
    }

    /**
     * 背包问题，回溯法解决
     * @param weight
     * @param v
     * @param W
     * @return
     */
    public static List<Integer> knapsackPath(int[] weight, int[] v, int W) {
        IntListValue maxPath = new IntListValue();
        knapsackPath0(weight, v, W, 0, new ArrayList<>(), maxPath);
        return maxPath.listValue;
    }

    private static void knapsackPath0(int[] weight, int[] v, int W, int n, List<Integer> path, IntListValue maxPath) {
        if (n == weight.length) {
            if (sum(path) > sum(maxPath.listValue)) {
                maxPath.listValue = new ArrayList<>(path);
            }
            return;
        }
        if (W < weight[n]) {
            if (sum(path) > sum(maxPath.listValue)) {
                maxPath.listValue = new ArrayList<>(path);
            }
            return;
        }

        knapsackPath0(weight, v, W, n + 1, path, maxPath); //0分支

        path.add(v[n]);
        knapsackPath0(weight, v, W - weight[n], n + 1, path, maxPath);  //1分支
        path.remove(path.size() - 1);
    }

    private static int sum(List<Integer> path) {
        if (null == path || path.size() == 0) {
            return 0;
        }

        int sum = 0;
        for (Integer i : path) {
            sum += i;
        }
        return sum;
    }

    /**
     * 背包问题 动态规划
     * dp[i][W]将前i件物品装入背包后的最大价值（组合问题，前i件物品，每件物品可装入0个或1个）
     * dp[i][j] = max(dp[i-1][j], v[i] + dp[i-1][j-weight[i]]])  j>=weight[i]
     *
     * bad case:
     * dp[0][W] = 0
     * dp[n][0] = 0
     * W <= 0, 则dp[n][W]=0
     * @param weight
     * @param v
     * @param W
     * @return
     */
    public static int knapsackDP(int[] weight, int[] v, int W) {
        int len = weight.length;
        int[][] dp = new int[len + 1][W + 1];

        for (int i = 0; i <= len; i++) {
            dp[i][0] = 0;
        }
        for (int j = 0; j <= W; j++) {
            dp[0][j] = 0;
        }

        for (int i = 1; i <= len; i++) {
            for (int j = 0; j <= W; j++) {
                int notChoosed = dp[i - 1][j];  //不选择第i件物品
                int choosed = 0;
                if (j >= weight[i - 1]) {
                    choosed = v[i - 1] + dp[i - 1][j - weight[i - 1]];  //选择第i件物品
                }

                dp[i][j] = Math.max(notChoosed, choosed);
            }
        }

        return dp[len][W];
    }

    /**
     * 背包问题 动态规划优化
     * 由上述状态转移方程可知，dp[i][j]的值只与dp[i-1][0,...,j-1]有关，
     * 所以我们可以采用动态规划常用的方法（滚动数组）对空间进行优化（即去掉dp的第一维）
     * 使用滚动数组优化时，只能逆序优化
     * @param weight
     * @param v
     * @param W
     * @return
     */
    public static int knapsackDP2(int[] weight, int[] v, int W) {
        int[] dp = new int[W + 1];
        for (int i = 0; i <= W; i++) {
            dp[i] = 0;
        }

        int len = weight.length;
        for (int i = 1; i <= len; i++) {
            for (int j = W; j >= weight[i - 1]; j--) {
                dp[j] = Math.max(dp[j], dp[j - weight[i - 1]] + v[i - 1]);
            }
        }

        return dp[W];
    }

    /**
     * 完全背包（unbounded knapsack problem）与01背包不同就是每种物品可以有无限多个：
     * 一共有N种物品，每种物品有无限多个，第i（i从1开始）种物品的重量为w[i]，价值为v[i]。
     * 在总重量不超过背包承载上限W的情况下，能够装入背包的最大价值是多少？
     *
     * dp[i][j]表示将前i件物品装入背包的最大价值（前i件物品，每件物品可装入0个或多个）
     * dp[i][j] = max(dp[i-1][j], dp[i][j - w[i]] + v[i]) （第i件物品可以装入0个或多个）
     * dp[0][j]=0
     * dp[i][0]=0
     * @param weight
     * @param v
     * @param W
     * @return
     */
    public static int knapscakComplete(int[] weight, int[] v, int W) {
        int len = weight.length;
        int[][] dp = new int[len + 1][W + 1];
        for (int i = 0; i <= len; i++) {
            dp[i][0] = 0;
        }
        for (int j = 0; j <= W; j++) {
            dp[0][j] = 0;
        }

        for (int i = 1; i <= len; i++) {
            for (int j = 1; j <= W; j++) {
                int notChoosed = dp[i - 1][j];
                int choosed = 0;
                if (j >= weight[i - 1]) {
                    choosed = dp[i][j - weight[i - 1]] + v[i - 1];
                }

                dp[i][j] = Math.max(choosed, notChoosed);
            }
        }

        return dp[len][W];
    }

    /**
     * 多重背包问题
     * 一共有N种物品，第i（i从1开始）种物品的数量为n[i]，重量为w[i]，价值为v[i]。
     * 在总重量不超过背包承载上限W的情况下，能够装入背包的最大价值是多少？
     *
     * 每件物品数量有限，最高数量为n[i]，设k=min(n[i], W/weight[i])，则每件物品装入数量为[0,k]
     * dp[i][j]表示前i件物品装入后的最大价值 （每件物品装入数量为[0,k]）
     * dp[i][j] = max(dp[i-1][j - k * w[i]] + k * v[i]), for 0<=k <= min(n[i], W/weight[i])
     * @param weight
     * @param n
     * @param v
     * @param W
     * @return
     */
    public static int knapsackBounded(int[] weight, int[] n, int[] v, int W) {
        int len = weight.length;
        int[][] dp = new int[len + 1][W + 1];
        for (int i = 0; i <= len; i++) {
            dp[i][0] = 0;
        }
        for (int j = 0; j <= W; j++) {
            dp[0][j] = 0;
        }

        for (int i = 1; i <= len; i++) {
            for (int j = 1; j <= W; j++) {
                int num = Math.min(n[i - 1], W / weight[i - 1]); //装入物品数量：[0,num]

                int maxDp = Integer.MIN_VALUE;
                for (int k = 0; k <= num; k++) { //装入k件物品
                    int choosed = 0;
                    if (j - k * weight[i - 1] >= 0) {
                        choosed = dp[i - 1][j - k * weight[i - 1]] + k * v[i - 1];
                    }

                    if (choosed > maxDp) {
                        maxDp = choosed;
                    }
                }

                dp[i][j] = maxDp;
            }
        }

        return dp[len][W];
    }

    public static void main(String[] args) {
        int[] weight = {1, 2, 3, 4, 10};
        int[] n = {2, 3, 3, 2, 2};
        int[] v = {20, 11, 22, 100, 1000};
        int W = 11;
        //System.out.println(knapsackDP(weight, v, W));
        //System.out.println(knapsackDP2(weight, v, W));
        //System.out.println(knapsack(weight, v, W));
        //System.out.println(knapsackPath(weight, v, W));

        int[] weight2 = {1, 2, 3, 4, 10};
        int[] n2 = {2, 3, 2, 2, 2};
        int[] v2 = {20, 11, 22, 100, 100};
        int W2 = 12;
        //System.out.println(knapsackDP(weight2, v2, W2));
        //System.out.println(knapsackDP2(weight, v2, W2));
        //System.out.println(knapsack(weight2, v2, W2));
        //System.out.println(knapsackPath(weight2, v2, W2));

        System.out.println(knapscakComplete(weight, v, W));
        System.out.println(knapscakComplete(weight2, v2, W2));

        //System.out.println(knapsackBounded(weight, n, v, W));
        System.out.println(knapsackBounded(weight2, n2, v2, W2));
    }
}
